package com.zzz.offer.step;

public class Step {
    public static void main(String[] args) {
        System.out.println(new Step().jumpFloor(4));
    }

    // 跳台阶问题 可以 把思路理解成
    // f(n) 跳n级台阶
    // f(n) 的第一次有两种，跳一阶  和  跳两阶
    // 跳一阶后  剩下 n-1 个台阶 这时是求f(n-1)
    // 跳两阶    剩下 n-2 个台阶 这时是求f(n-2)
    // 于是f(n) = f(n-1) + f(n-2)
    // 思维的转变才是最重要的
    // 我一直在纠结 跳了 1 次，身下n-1  和 跳 2 次 剩下怎么排列，就是不会把思维转换 f(n-1) f(n-2)
    // 找不到 子问题 的定义
    public int jumpFloor(int target) {

        if (target == 0) {
            return 0;
        }
        int first = 1;
        int second = 2;
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }

        int result = 0;
        for (int i = 3; i <= target; i++) {
            result = second + first;
            first = second;
            second = result;
        }
        return result;
    }
}
